package chapter02_linkedList;

/**
 * 描述：
 *      约瑟夫环形链表问题
 * @author hl
 * @date 2021/1/26 10:10
 */
public class JosephusKill {
    /**
     * 每次遍历m次后删除一个结点，时间复杂度为O(n * m)
     * @param head
     * @param m
     * @return
     */
    public Node josephusKill1(Node head, int m){
        if (head == null || head.next == null || m < 1) {
            return head;
        }
        Node last = head;
        while(last.next != head){
            last = last.next;
        }
        int count = 0;
        while(last != head){
            if (++count == m) {
                last.next = head.next;
                count = 0;
            }else{
                last = last.next;
            }
            head = last.next;
        }
        return head;
    }

    /**
     * 递推：
     *      在只剩一个结点的时候，这个幸存结点的编号为Num(1) = 1
     *      在由两个结点组成的环中，假设幸存者结点的编号为Num(2);
     *      .....
     *      在由n个结点组成的环中，假设幸存者节点的编号为Num(n);
     *      我们已经知道Num(1) = 1，如果可以求出Num(i- 1)和Num(i)的关系，那么我们通过递归求出Num(n).
     *      Num(i) = (Num(i - 1) + m - 1) % i + 1;
     * @param head
     * @param m
     * @return
     */
    public Node josephusKill2(Node head, int m){
        if (head == null || head.next == null || m < 1) {
            return head;
        }
        int temp = 0;//list size
        Node cur = head;
        while(cur != null){
            cur = cur.next;
            temp++;
        }
        int Num = getNum(m, temp);
        return null;
    }

    private int getNum(int m, int i) {
        if (i == 1) {
            return 1;
        }
        return (getNum(m, i - 1) + m - 1) % i + 1;
    }

}
